package com.wzw.basics.concurrent.aqs;

import sun.misc.Unsafe;

import java.util.ArrayList;
import java.util.Collection;
import java.util.Date;
import java.util.concurrent.TimeUnit;
import java.util.concurrent.locks.*;

/**
 * public abstract class resolve
 * extends AbstractOwnableSynchronizer
 * implements java.io.Serializable
 * <p>
 * 多个线程对共享资源，进行访问加锁时会导致有且仅有一个线程能拿到资源。其余的线程会被阻塞，就需要排队去争抢资源。
 *
 * <p>
 * 抽象队列同步器，是JUC中一切线程阻塞队列的基础框架。通过内置的FIFO队列来完成资源获取线程的排队工作，并通过一个int类型变量表示持有锁的状态。
 * 如果共享资源被占用，就需要一定的阻塞等待唤醒机制来保证锁分配。
 * 这个机制主要用的是CLH队列的变体实现的，将暂时获取不到锁的线程加入到队列中，这个队列就是AQS的抽象表现。
 * 它将请求共享资源的线程封装成队列的结点(Node)，通过CAS、自旋以及LockSupport.park()与unpark的方式，维护state变量的状态，使并发达到同步的控制效果。
 * <p>
 * 进一步理解锁和同步器的关系
 * 锁，面向锁的使用者 - 定义了程序员和锁交互的使用层API，隐藏了实现细节，你调用即可
 * 同步器，面向锁的实现者 - 比如Java并发大神DougLee，提出统一规范并简化了锁的实现，屏蔽了同步状态管理、阻塞线程排队和通知、唤醒机制等。
 *
 * <p>
 * 能干嘛？
 * 加锁会导致阻塞 - 有阻塞就需要排队，实现排队必然需要有某种形式的队列来进行管理
 * <p>
 * 解释说明
 *
 * @author Wangzhiwen
 */
public class AQS {

    public static void main(String[] args) {
        // ReentrantLock 实现了AQS
        ReentrantLock reentrantLock = new ReentrantLock();
        // 非公平锁
        reentrantLock.lock();
        reentrantLock.lockInterruptibly();
        Condition condition = reentrantLock.newCondition();
        condition.await();
        System.out.println("---------------");
        reentrantLock.unlock();
        // 公平锁
        ReentrantLock fairLock = new ReentrantLock(true);
        fairLock.tryLock();
        fairLock.lock();
        demo();
    }

    public static final Lock LOCK = new ReentrantLock(false); // 使用非公平锁

    /**
     * 从AQS的实现类 ReentrantLock 来解析AQS工作的原理。
     * AQS框架，采用模板方法模式，已经抽象好了全部的功能。
     * 内部实现已经了线程同步状态标识state修改以及线程阻塞、入队、唤醒的全部功能。
     * 我们只需要，根据需求实现其指定的 tryAcquire tryRelease tryAcquireShared tryReleaseShared isHeldExclusively 等方法。
     * 顶层定义的 acquire release 方法是模板方法。会把具体实现延迟到子类中
     */
    public static void demo() {
        /*
         * 假如有三个线程操作同一资源类Resource，使用ReentrantLock加锁保证同步
         */
        Resource resource = new Resource(1, "1");

        new Operate(resource, "Thread A").start();
        new Operate(resource, "Thread B").start();
        new Operate(resource, "Thread C").start();
    }

}

class Resource {
    private int number;
    private String name;

    public Resource(int number, String name) {
        this.number = number;
        this.name = name;
    }

    public int getNumber() {
        return number;
    }

    public void setNumber(int number) {
        this.number = number;
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    @Override
    public String toString() {
        return "Resource{" + "number=" + number + ", name='" + name + '\'' + '}';
    }
}

class Operate extends Thread {

    private Resource resource;

    public Operate(Resource resource, String name) {
        super(name);
        this.resource = resource;
    }

    /*
     * 关键方法：
     * ReentrantLock -->
     *
     *          final void lock() {
     *             if (compareAndSetState(0, 1)) CAS设置同步器中的state标识为1，如果设置成功就代表当前线程抢占到了锁资源
     *                 setExclusiveOwnerThread(Thread.currentThread()); 设置独占锁的线程为当前线程，这个方法是在AQS的父类中实现的。记录当前占用锁的线程
     *             else 如果没有抢占到锁资源，则尝试再次获取锁
     *                 acquire(1);  这个方法是AQS中定义的模板方法
     *         }
     *
     *         protected final boolean tryAcquire(int acquires) {
     *             return nonfairTryAcquire(acquires); 调用父类同步去Sync中的方法
     *         }
     *
     *         final boolean nonfairTryAcquire(int acquires) {
     *             final Thread current = Thread.currentThread(); 获取当前线程
     *             int c = getState(); 获取当前AQS中锁的同步状态
     *             if (c == 0) { 如果为0，代表锁可用。这里有可能在第一次CAS过程没抢到锁，然后上一个线程立马释放了锁。
     *                 if (compareAndSetState(0, acquires)) { 再次CAS设置state标识位为1
     *                     setExclusiveOwnerThread(current); 如果设置成功，把当前锁的独占线程设置自己
     *                     return true; 抢到了锁，返回true
     *                 }
     *             }
     *             else if (current == getExclusiveOwnerThread()) { 当前state不为0，判断当前线程是不是占有锁的线程。如果是，则把state做加法。这里也是ReentrantLock是重入锁的原理
     *                 int nextc = c + acquires;
     *                 if (nextc < 0) // overflow
     *                     throw new Error("Maximum lock count exceeded");
     *                 setState(nextc);
     *                 return true; 同一个线程可以重复持有同一把锁，返回true
     *             }
     *             return false; 没有抢到锁，准备进入阻塞队列
     *         }
     *
     * AQS --->
     *
     *         public final void acquire(int arg) {
     *             if (
     *             !tryAcquire(arg) 再次尝试获取锁资源。这是AQS里的钩子方法，必须有子类实现。进入到ReentrantLock中
     *                  &&
     *             acquireQueued( 再次尝试获取锁失败后，准备加入阻塞等待队列。传入内部类Node的静态属性，static final Node EXCLUSIVE = null;
     *                  addWaiter(Node.EXCLUSIVE), arg)
     *                          )
     *             selfInterrupt(); 线程被阻塞被中断后调用次方法，直接中断线程
     *         }
     *
     *         Node(Thread thread, Node mode) {     // Used by addWaiter
     *             this.nextWaiter = mode;
     *             this.thread = thread;
     *         }
     *
     *         private Node addWaiter(Node mode) {
     *              Node node = new Node(Thread.currentThread(), mode); mode为null，创建一个Node等待对象
     *              Node pred = tail;  获取当前队列的尾结点
     *              if (pred != null) { 第一个节点入队时，队列内还没有任何节点尾结点为null。尾结点不为null时才进入if块内
     *                  node.prev = pred; 把当前新建的等待节点node前驱设为尾结点，简单来说就是入队排队在队列最尾部。
     *                 if (compareAndSetTail(pred, node)) { CAS设置队列的尾节点为node
     *                      pred.next = node;
     *                      return node;
     *                   }
     *              }
     *              enq(node); 队列尾节点为null时，进入enq方法
     *              return node;
     *         }
     *
     *         // CAS head field. Used only by enq.
     *         private final boolean compareAndSetHead(Node update) {
     *              return unsafe.compareAndSwapObject(this, headOffset, null, update);
     *         }
     *
     *         // 队列的初始化方法，只有队列为空时才会调用此方法。结果是会创建一个头结点为傀儡节点，尾结点为thread节点的队列
     *         private Node enq(final Node node) {
     *          for (;;) {  自旋，第一个thread进入时，第一次循环走的是 t==null的逻辑，队列被初始化了；第二次循环走的是 t != null的逻辑，把thread设为尾结点。
     *             Node t = tail; 获取当前队列的尾结点
     *             if (t == null) { // Must initialize 尾节点为null时，即代表当前队列为空必须初始化
     *                 if (compareAndSetHead(new Node())) 队列初始化时，设置当前队列头结点为 虚节点（傀儡节点）。即只有一个占位的功能，真正带有线程的节点是从队列第二个开始
     *                     tail = head; 头结点赋值尾结点，即当前队列头结点与尾结点都是同一个node
     *             } else { 尾节点不为null时，设置当前准备入队的节点node为尾结点。与addWaiter方法中逻辑相同，目的时第二次循环时。队列已被初始化，会走到这一步
     *                 node.prev = t;
     *                 if (compareAndSetTail(t, node)) { 设置thread节点为尾结点
     *                     t.next = node;
     *                     return t;
     *                 }
     *             }
     *           }
     *        }
     *
     *       // 设置头结点为傀儡节点
     *       private void setHead(Node node) {
     *          head = node;
     *          node.thread = null;
     *          node.prev = null;
     *        }
     *
     *        // addWaiter方法创建等待节点node后，进入此方法。这里实现节点被阻塞的逻辑。返回类型代表线程是否被中断了
     *        final boolean acquireQueued(final Node node, int arg) {
     *          boolean failed = true; 失败标识
     *          try {
     *              boolean interrupted = false; 线程是否被中断的标识
     *              for (;;) { 自旋
     *                  final Node p = node.predecessor(); 获取当前等待节点node的前驱节点
     *                   if (p == head && tryAcquire(arg)) {  当前等待节点的前驱节点等于头结点时再次抢锁。第一个thread进入队列后，它的前驱节点刚好是头结点。
     *                         setHead(node); 抢锁成功，设置头结点（傀儡节点为）为当前节点
     *                         p.next = null; // help GC 把头结点也就是傀儡节点和当前节点的指针关系置空，方便GC回收。
     *                         failed = false;
     *                         return interrupted;
     *                     }
     *                   if (shouldParkAfterFailedAcquire(p, node) && 抢锁失败后设置node的前驱节点的等待状态为 -1 signal
     *                       parkAndCheckInterrupt()) 阻塞线程
     *                       interrupted = true;
     *              }
     *           }finally {
     *               if (failed)
     *                   cancelAcquire(node);
     *           }
     *        }
     *
     *        // pred node的前驱 node 包含线程的等待节点
     *        private static boolean shouldParkAfterFailedAcquire(Node pred, Node node) {
     *          int ws = pred.waitStatus; 初始状态为 0
     *          if (ws == Node.SIGNAL)
     *             return true; 状态为 -1 就返回 true
     *          if (ws > 0) {
     *              do {
     *                 node.prev = pred = pred.prev;
     *              } while (pred.waitStatus > 0);
     *                 pred.next = node;
     *          } else { 设置状态为 -1
     *             compareAndSetWaitStatus(pred, ws, Node.SIGNAL);
     *          }
     *          return false;
     *        }
     *
     *        阻塞线程
     *        private final boolean parkAndCheckInterrupt() {
     *          LockSupport.park(this);
     *          return Thread.interrupted();
     *        }
     *
     * ReentrantLock.unlock() --->
     *
     *        public void unlock() {
     *             sync.release(1);
     *        }
     *
     *        protected final boolean tryRelease(int releases) {
     *             int c = getState() - releases; 相减
     *             if (Thread.currentThread() != getExclusiveOwnerThread()) 如果当前线程不是占有锁的线程会抛出异常
     *                 throw new IllegalMonitorStateException();
     *             boolean free = false; 锁资源是否释放
     *             if (c == 0) { 标识为0 代表锁已释放，置空队列中独占锁的线程
     *                 free = true;
     *                 setExclusiveOwnerThread(null);
     *             }
     *             setState(c); 设置队列中 同步资源标识state
     *             return free; 返回释放结果
     *        }
     *
     * AQS.release() --->
     *
     *        public final boolean release(int arg) {
     *          if (tryRelease(arg)) { 钩子方法调用子类的具体实现
     *              Node h = head;
     *              if (h != null && h.waitStatus != 0)
     *                  unparkSuccessor(h); 唤醒队列中傀儡节点后面的thread节点
     *              return true;
     *          }
     *          return false;
     *        }
     *
     *        private void unparkSuccessor(Node node) {
     *            int ws = node.waitStatus;
     *            if (ws < 0){
     *                compareAndSetWaitStatus(node, ws, 0); 重置傀儡节点的等待状态为0
     *            }
     *            Node s = node.next; 拿到带有thread的等待节点
     *            if (s == null || s.waitStatus > 0) {
     *                s = null;
     *                for (Node t = tail; t != null && t != node; t = t.prev)
     *                     if (t.waitStatus <= 0)
     *                          s = t;
     *            }
     *            if (s != null) 节点不为null，唤醒节点。节点被唤醒后会继续进行acquireQueued方法里的循环，抢锁成功后就可以正确执行了
     *               LockSupport.unpark(s.thread);
     *        }
     *
     */
    @Override
    public void run() {
        /*
         * ReentrantLock实现了Lock接口，并在其内部聚合了一个继承了AQS类的同步器Sync。Lock下基本所有的实现类都是在内部聚合了实现AQS的同步器，来控制线程同步
         * lock()方法
         *     1.调用内部Sync同步器的非公平锁实现类 NonfairSync.lock()方法
         *
         */
        AQS.LOCK.lock();
        try {
            resource.setNumber(2);
            resource.setName(Thread.currentThread().getName());
            System.out.println(resource);
        } catch (Exception e) {
            // ignore
        } finally {
            AQS.LOCK.unlock();
        }
    }
}

class resolve extends AbstractOwnableSynchronizer implements java.io.Serializable {

    private static final long serialVersionUID = 7373984972572414691L;

    protected resolve() {
    }

    /**
     * 封装线程及线程阻塞状态的节点
     * 内部包含其 前驱节点与后继节点 构成一个双向的 FIFO CLH 队列
     */
    static final class Node {
        /**
         * 表示线程以共享的模式等待锁
         */
        static final resolve.Node SHARED = new resolve.Node();
        /**
         * 表示线程正在以独占的方式等待锁
         */
        static final resolve.Node EXCLUSIVE = null;

        /**
         * 表示线程取消
         * waitStatus value to indicate thread has cancelled
         */
        static final int CANCELLED = 1;
        /**
         * 后继线程需要唤醒
         * waitStatus value to indicate successor's thread needs unparking
         */
        static final int SIGNAL = -1;
        /**
         * 等待condition唤醒
         * waitStatus value to indicate thread is waiting on condition
         */
        static final int CONDITION = -2;
        /**
         * 共享式同步状态获取将会无条件地传播下去
         * waitStatus value to indicate the next acquireShared should
         * unconditionally propagate
         */
        static final int PROPAGATE = -3;

        /**
         * 当前节点在队列中的状态（重点）
         * 等候区其它顾客(其它线程)的等待状态
         * 队列中每个排队的个体就是一个Node，初始为0，状态上面的几种
         */
        volatile int waitStatus;

        /**
         * 前驱节点（重点）
         */
        volatile resolve.Node prev;

        /**
         * 后继节点（重点）
         */
        volatile resolve.Node next;

        /**
         * 表示处于该节点的线程
         */
        volatile Thread thread;

        /**
         * 指向下一个处于CONDITION状态的节点
         */
        resolve.Node nextWaiter;

        /**
         * 是否是共享锁
         */
        final boolean isShared() {
            return nextWaiter == SHARED;
        }

        /**
         * Returns previous node, or throws NullPointerException if null.
         * Use when predecessor cannot be null.  The null check could
         * be elided, but is present to help the VM.
         *
         * @return the predecessor of this node
         */
        final resolve.Node predecessor() throws NullPointerException {
            resolve.Node p = prev;
            if (p == null) throw new NullPointerException();
            else return p;
        }

        Node() {    // Used to establish initial head or SHARED marker
        }

        Node(Thread thread, resolve.Node mode) {     // Used by addWaiter
            this.nextWaiter = mode;
            this.thread = thread;
        }

        Node(Thread thread, int waitStatus) { // Used by Condition
            this.waitStatus = waitStatus;
            this.thread = thread;
        }
    }

    /**
     * 队列的头结点
     * Head of the wait queue, lazily initialized.  Except for
     * initialization, it is modified only via method setHead.  Note:
     * If head exists, its waitStatus is guaranteed not to be
     * CANCELLED.
     */
    private transient volatile resolve.Node head;

    /**
     * 队列的尾结点
     * Tail of the wait queue, lazily initialized.  Modified only via
     * method enq to add new wait node.
     */
    private transient volatile resolve.Node tail;

    /**
     * 线程的同步状态，初始为0. 0代表可以使用 非0代表已被占用其他线程需要等待
     * The synchronization state.
     */
    private volatile int state;

    /**
     * Returns the current value of synchronization state.
     * This operation has memory semantics of a {@code volatile} read.
     *
     * @return current state value
     */
    protected final int getState() {
        return state;
    }

    /**
     * Sets the value of synchronization state.
     * This operation has memory semantics of a {@code volatile} write.
     *
     * @param newState the new state value
     */
    protected final void setState(int newState) {
        state = newState;
    }

    /**
     * Atomically sets synchronization state to the given updated
     * value if the current state value equals the expected value.
     * This operation has memory semantics of a {@code volatile} read
     * and write.
     *
     * @param expect the expected value
     * @param update the new value
     * @return {@code true} if successful. False return indicates that the actual
     * value was not equal to the expected value.
     */
    protected final boolean compareAndSetState(int expect, int update) {
        // See below for intrinsics setup to support this
        return unsafe.compareAndSwapInt(this, stateOffset, expect, update);
    }

    // Queuing utilities

    /**
     * The number of nanoseconds for which it is faster to spin
     * rather than to use timed park. A rough estimate suffices
     * to improve responsiveness with very short timeouts.
     */
    static final long spinForTimeoutThreshold = 1000L;

    /**
     * Inserts node into queue, initializing if necessary. See picture above.
     *
     * @param node the node to insert
     * @return node's predecessor
     */
    private resolve.Node enq(final resolve.Node node) {
        for (; ; ) {
            resolve.Node t = tail;
            if (t == null) { // Must initialize
                if (compareAndSetHead(new resolve.Node())) tail = head;
            } else {
                node.prev = t;
                if (compareAndSetTail(t, node)) {
                    t.next = node;
                    return t;
                }
            }
        }
    }

    /**
     * Creates and enqueues node for current thread and given mode.
     *
     * @param mode Node.EXCLUSIVE for exclusive, Node.SHARED for shared
     * @return the new node
     */
    private resolve.Node addWaiter(resolve.Node mode) {
        resolve.Node node = new resolve.Node(Thread.currentThread(), mode);
        // Try the fast path of enq; backup to full enq on failure
        resolve.Node pred = tail;
        if (pred != null) {
            node.prev = pred;
            if (compareAndSetTail(pred, node)) {
                pred.next = node;
                return node;
            }
        }
        enq(node);
        return node;
    }

    /**
     * Sets head of queue to be node, thus dequeuing. Called only by
     * acquire methods.  Also nulls out unused fields for sake of GC
     * and to suppress unnecessary signals and traversals.
     *
     * @param node the node
     */
    private void setHead(resolve.Node node) {
        head = node;
        node.thread = null;
        node.prev = null;
    }

    /**
     * Wakes up node's successor, if one exists.
     *
     * @param node the node
     */
    private void unparkSuccessor(resolve.Node node) {
        /*
         * If status is negative (i.e., possibly needing signal) try
         * to clear in anticipation of signalling.  It is OK if this
         * fails or if status is changed by waiting thread.
         */
        int ws = node.waitStatus;
        if (ws < 0) compareAndSetWaitStatus(node, ws, 0);

        /*
         * Thread to unpark is held in successor, which is normally
         * just the next node.  But if cancelled or apparently null,
         * traverse backwards from tail to find the actual
         * non-cancelled successor.
         */
        resolve.Node s = node.next;
        if (s == null || s.waitStatus > 0) {
            s = null;
            for (resolve.Node t = tail; t != null && t != node; t = t.prev)
                if (t.waitStatus <= 0) s = t;
        }
        if (s != null) LockSupport.unpark(s.thread);
    }

    /**
     * Release action for shared mode -- signals successor and ensures
     * propagation. (Note: For exclusive mode, release just amounts
     * to calling unparkSuccessor of head if it needs signal.)
     */
    private void doReleaseShared() {
        /*
         * Ensure that a release propagates, even if there are other
         * in-progress acquires/releases.  This proceeds in the usual
         * way of trying to unparkSuccessor of head if it needs
         * signal. But if it does not, status is set to PROPAGATE to
         * ensure that upon release, propagation continues.
         * Additionally, we must loop in case a new node is added
         * while we are doing this. Also, unlike other uses of
         * unparkSuccessor, we need to know if CAS to reset status
         * fails, if so rechecking.
         */
        for (; ; ) {
            resolve.Node h = head;
            if (h != null && h != tail) {
                int ws = h.waitStatus;
                if (ws == resolve.Node.SIGNAL) {
                    if (!compareAndSetWaitStatus(h, resolve.Node.SIGNAL, 0))
                        continue;            // loop to recheck cases
                    unparkSuccessor(h);
                } else if (ws == 0 && !compareAndSetWaitStatus(h, 0, resolve.Node.PROPAGATE))
                    continue;                // loop on failed CAS
            }
            if (h == head)                   // loop if head changed
                break;
        }
    }

    /**
     * Sets head of queue, and checks if successor may be waiting
     * in shared mode, if so propagating if either propagate > 0 or
     * PROPAGATE status was set.
     *
     * @param node      the node
     * @param propagate the return value from a tryAcquireShared
     */
    private void setHeadAndPropagate(resolve.Node node, int propagate) {
        resolve.Node h = head; // Record old head for check below
        setHead(node);
        /*
         * Try to signal next queued node if:
         *   Propagation was indicated by caller,
         *     or was recorded (as h.waitStatus either before
         *     or after setHead) by a previous operation
         *     (note: this uses sign-check of waitStatus because
         *      PROPAGATE status may transition to SIGNAL.)
         * and
         *   The next node is waiting in shared mode,
         *     or we don't know, because it appears null
         *
         * The conservatism in both of these checks may cause
         * unnecessary wake-ups, but only when there are multiple
         * racing acquires/releases, so most need signals now or soon
         * anyway.
         */
        if (propagate > 0 || h == null || h.waitStatus < 0 || (h = head) == null || h.waitStatus < 0) {
            resolve.Node s = node.next;
            if (s == null || s.isShared()) doReleaseShared();
        }
    }

    // Utilities for various versions of acquire

    /**
     * Cancels an ongoing attempt to acquire.
     *
     * @param node the node
     */
    private void cancelAcquire(resolve.Node node) {
        // Ignore if node doesn't exist
        if (node == null) return;

        node.thread = null;

        // Skip cancelled predecessors
        resolve.Node pred = node.prev;
        while (pred.waitStatus > 0) node.prev = pred = pred.prev;

        // predNext is the apparent node to unsplice. CASes below will
        // fail if not, in which case, we lost race vs another cancel
        // or signal, so no further action is necessary.
        resolve.Node predNext = pred.next;

        // Can use unconditional write instead of CAS here.
        // After this atomic step, other Nodes can skip past us.
        // Before, we are free of interference from other threads.
        node.waitStatus = resolve.Node.CANCELLED;

        // If we are the tail, remove ourselves.
        if (node == tail && compareAndSetTail(node, pred)) {
            compareAndSetNext(pred, predNext, null);
        } else {
            // If successor needs signal, try to set pred's next-link
            // so it will get one. Otherwise wake it up to propagate.
            int ws;
            if (pred != head && ((ws = pred.waitStatus) == resolve.Node.SIGNAL || (ws <= 0 && compareAndSetWaitStatus(pred, ws, resolve.Node.SIGNAL))) && pred.thread != null) {
                resolve.Node next = node.next;
                if (next != null && next.waitStatus <= 0) compareAndSetNext(pred, predNext, next);
            } else {
                unparkSuccessor(node);
            }

            node.next = node; // help GC
        }
    }

    /**
     * Checks and updates status for a node that failed to acquire.
     * Returns true if thread should block. This is the main signal
     * control in all acquire loops.  Requires that pred == node.prev.
     *
     * @param pred node's predecessor holding status
     * @param node the node
     * @return {@code true} if thread should block
     */
    private static boolean shouldParkAfterFailedAcquire(resolve.Node pred, resolve.Node node) {
        int ws = pred.waitStatus;
        if (ws == resolve.Node.SIGNAL)
            /*
             * This node has already set status asking a release
             * to signal it, so it can safely park.
             */ return true;
        if (ws > 0) {
            /*
             * Predecessor was cancelled. Skip over predecessors and
             * indicate retry.
             */
            do {
                node.prev = pred = pred.prev;
            } while (pred.waitStatus > 0);
            pred.next = node;
        } else {
            /*
             * waitStatus must be 0 or PROPAGATE.  Indicate that we
             * need a signal, but don't park yet.  Caller will need to
             * retry to make sure it cannot acquire before parking.
             */
            compareAndSetWaitStatus(pred, ws, resolve.Node.SIGNAL);
        }
        return false;
    }

    /**
     * Convenience method to interrupt current thread.
     */
    static void selfInterrupt() {
        Thread.currentThread().interrupt();
    }

    /**
     * Convenience method to park and then check if interrupted
     *
     * @return {@code true} if interrupted
     */
    private final boolean parkAndCheckInterrupt() {
        LockSupport.park(this);
        return Thread.interrupted();
    }

    /*
     * Various flavors of acquire, varying in exclusive/shared and
     * control modes.  Each is mostly the same, but annoyingly
     * different.  Only a little bit of factoring is possible due to
     * interactions of exception mechanics (including ensuring that we
     * cancel if tryAcquire throws exception) and other control, at
     * least not without hurting performance too much.
     */

    /**
     * 定义在最顶层的模板方法
     * Acquires in exclusive uninterruptible mode for thread already in
     * queue. Used by condition wait methods as well as acquire.
     *
     * @param node the node
     * @param arg  the acquire argument
     * @return {@code true} if interrupted while waiting
     */
    final boolean acquireQueued(final resolve.Node node, int arg) {
        boolean failed = true;
        try {
            boolean interrupted = false;
            for (; ; ) {
                final resolve.Node p = node.predecessor();
                if (p == head && tryAcquire(arg)) {
                    setHead(node);
                    p.next = null; // help GC
                    failed = false;
                    return interrupted;
                }
                if (shouldParkAfterFailedAcquire(p, node) && parkAndCheckInterrupt()) interrupted = true;
            }
        } finally {
            if (failed) cancelAcquire(node);
        }
    }

    /**
     * Acquires in exclusive interruptible mode.
     *
     * @param arg the acquire argument
     */
    private void doAcquireInterruptibly(int arg) throws InterruptedException {
        final resolve.Node node = addWaiter(resolve.Node.EXCLUSIVE);
        boolean failed = true;
        try {
            for (; ; ) {
                final resolve.Node p = node.predecessor();
                if (p == head && tryAcquire(arg)) {
                    setHead(node);
                    p.next = null; // help GC
                    failed = false;
                    return;
                }
                if (shouldParkAfterFailedAcquire(p, node) && parkAndCheckInterrupt()) throw new InterruptedException();
            }
        } finally {
            if (failed) cancelAcquire(node);
        }
    }

    /**
     * Acquires in exclusive timed mode.
     *
     * @param arg          the acquire argument
     * @param nanosTimeout max wait time
     * @return {@code true} if acquired
     */
    private boolean doAcquireNanos(int arg, long nanosTimeout) throws InterruptedException {
        if (nanosTimeout <= 0L) return false;
        final long deadline = System.nanoTime() + nanosTimeout;
        final resolve.Node node = addWaiter(resolve.Node.EXCLUSIVE);
        boolean failed = true;
        try {
            for (; ; ) {
                final resolve.Node p = node.predecessor();
                if (p == head && tryAcquire(arg)) {
                    setHead(node);
                    p.next = null; // help GC
                    failed = false;
                    return true;
                }
                nanosTimeout = deadline - System.nanoTime();
                if (nanosTimeout <= 0L) return false;
                if (shouldParkAfterFailedAcquire(p, node) && nanosTimeout > spinForTimeoutThreshold)
                    LockSupport.parkNanos(this, nanosTimeout);
                if (Thread.interrupted()) throw new InterruptedException();
            }
        } finally {
            if (failed) cancelAcquire(node);
        }
    }

    /**
     * Acquires in shared uninterruptible mode.
     *
     * @param arg the acquire argument
     */
    private void doAcquireShared(int arg) {
        final resolve.Node node = addWaiter(resolve.Node.SHARED);
        boolean failed = true;
        try {
            boolean interrupted = false;
            for (; ; ) {
                final resolve.Node p = node.predecessor();
                if (p == head) {
                    int r = tryAcquireShared(arg);
                    if (r >= 0) {
                        setHeadAndPropagate(node, r);
                        p.next = null; // help GC
                        if (interrupted) selfInterrupt();
                        failed = false;
                        return;
                    }
                }
                if (shouldParkAfterFailedAcquire(p, node) && parkAndCheckInterrupt()) interrupted = true;
            }
        } finally {
            if (failed) cancelAcquire(node);
        }
    }

    /**
     * Acquires in shared interruptible mode.
     *
     * @param arg the acquire argument
     */
    private void doAcquireSharedInterruptibly(int arg) throws InterruptedException {
        final resolve.Node node = addWaiter(resolve.Node.SHARED);
        boolean failed = true;
        try {
            for (; ; ) {
                final resolve.Node p = node.predecessor();
                if (p == head) {
                    int r = tryAcquireShared(arg);
                    if (r >= 0) {
                        setHeadAndPropagate(node, r);
                        p.next = null; // help GC
                        failed = false;
                        return;
                    }
                }
                if (shouldParkAfterFailedAcquire(p, node) && parkAndCheckInterrupt()) throw new InterruptedException();
            }
        } finally {
            if (failed) cancelAcquire(node);
        }
    }

    /**
     * Acquires in shared timed mode.
     *
     * @param arg          the acquire argument
     * @param nanosTimeout max wait time
     * @return {@code true} if acquired
     */
    private boolean doAcquireSharedNanos(int arg, long nanosTimeout) throws InterruptedException {
        if (nanosTimeout <= 0L) return false;
        final long deadline = System.nanoTime() + nanosTimeout;
        final resolve.Node node = addWaiter(resolve.Node.SHARED);
        boolean failed = true;
        try {
            for (; ; ) {
                final resolve.Node p = node.predecessor();
                if (p == head) {
                    int r = tryAcquireShared(arg);
                    if (r >= 0) {
                        setHeadAndPropagate(node, r);
                        p.next = null; // help GC
                        failed = false;
                        return true;
                    }
                }
                nanosTimeout = deadline - System.nanoTime();
                if (nanosTimeout <= 0L) return false;
                if (shouldParkAfterFailedAcquire(p, node) && nanosTimeout > spinForTimeoutThreshold)
                    LockSupport.parkNanos(this, nanosTimeout);
                if (Thread.interrupted()) throw new InterruptedException();
            }
        } finally {
            if (failed) cancelAcquire(node);
        }
    }

    // Main exported methods
    // 交由子类去实现，主要是对内部同步状态 state 值的设置，然后再去调用AQS类中已经封装好的线程排队、唤醒方法

    /**
     * 采用的是模板方法设计模式
     * 把具体抽象的方法交由子类去实现
     * <p>
     * 尝试获取锁
     */
    protected boolean tryAcquire(int arg) {
        throw new UnsupportedOperationException();
    }

    /**
     * 释放锁
     */
    protected boolean tryRelease(int arg) {
        throw new UnsupportedOperationException();
    }

    /**
     * 获取独占锁
     */
    protected int tryAcquireShared(int arg) {
        throw new UnsupportedOperationException();
    }

    /**
     * 释放共享锁
     */
    protected boolean tryReleaseShared(int arg) {
        throw new UnsupportedOperationException();
    }

    /**
     * 判断是否是独占锁
     */
    protected boolean isHeldExclusively() {
        throw new UnsupportedOperationException();
    }

    /**
     * 核心模板方法，
     * 1.tryAcquire 是由子类实现的获取锁的方式，公平或者非公平
     * 2.acquireQueued 自旋获取锁，第一次tryAcquire获取锁失败时。再次尝试获取锁
     * 3.addWaiter 加入等待队列
     * 4.selfInterrupt 都失败时终端当前线程
     * <p>
     * Acquires in exclusive mode, ignoring interrupts.  Implemented
     * by invoking at least once {@link #tryAcquire},
     * returning on success.  Otherwise the thread is queued, possibly
     * repeatedly blocking and unblocking, invoking {@link
     * #tryAcquire} until success.  This method can be used
     * to implement method {@link Lock#lock}.
     *
     * @param arg the acquire argument.  This value is conveyed to
     *            {@link #tryAcquire} but is otherwise uninterpreted and
     *            can represent anything you like.
     */
    public final void acquire(int arg) {
        if (!tryAcquire(arg) && acquireQueued(addWaiter(resolve.Node.EXCLUSIVE), arg)) selfInterrupt();
    }

    /**
     * Acquires in exclusive mode, aborting if interrupted.
     * Implemented by first checking interrupt status, then invoking
     * at least once {@link #tryAcquire}, returning on
     * success.  Otherwise the thread is queued, possibly repeatedly
     * blocking and unblocking, invoking {@link #tryAcquire}
     * until success or the thread is interrupted.  This method can be
     * used to implement method {@link Lock#lockInterruptibly}.
     *
     * @param arg the acquire argument.  This value is conveyed to
     *            {@link #tryAcquire} but is otherwise uninterpreted and
     *            can represent anything you like.
     * @throws InterruptedException if the current thread is interrupted
     */
    public final void acquireInterruptibly(int arg) throws InterruptedException {
        if (Thread.interrupted()) throw new InterruptedException();
        if (!tryAcquire(arg)) doAcquireInterruptibly(arg);
    }

    /**
     * Attempts to acquire in exclusive mode, aborting if interrupted,
     * and failing if the given timeout elapses.  Implemented by first
     * checking interrupt status, then invoking at least once {@link
     * #tryAcquire}, returning on success.  Otherwise, the thread is
     * queued, possibly repeatedly blocking and unblocking, invoking
     * {@link #tryAcquire} until success or the thread is interrupted
     * or the timeout elapses.  This method can be used to implement
     * method {@link Lock#tryLock(long, TimeUnit)}.
     *
     * @param arg          the acquire argument.  This value is conveyed to
     *                     {@link #tryAcquire} but is otherwise uninterpreted and
     *                     can represent anything you like.
     * @param nanosTimeout the maximum number of nanoseconds to wait
     * @return {@code true} if acquired; {@code false} if timed out
     * @throws InterruptedException if the current thread is interrupted
     */
    public final boolean tryAcquireNanos(int arg, long nanosTimeout) throws InterruptedException {
        if (Thread.interrupted()) throw new InterruptedException();
        return tryAcquire(arg) || doAcquireNanos(arg, nanosTimeout);
    }

    /**
     * Releases in exclusive mode.  Implemented by unblocking one or
     * more threads if {@link #tryRelease} returns true.
     * This method can be used to implement method {@link Lock#unlock}.
     *
     * @param arg the release argument.  This value is conveyed to
     *            {@link #tryRelease} but is otherwise uninterpreted and
     *            can represent anything you like.
     * @return the value returned from {@link #tryRelease}
     */
    public final boolean release(int arg) {
        if (tryRelease(arg)) {
            resolve.Node h = head;
            if (h != null && h.waitStatus != 0) unparkSuccessor(h);
            return true;
        }
        return false;
    }

    /**
     * Acquires in shared mode, ignoring interrupts.  Implemented by
     * first invoking at least once {@link #tryAcquireShared},
     * returning on success.  Otherwise the thread is queued, possibly
     * repeatedly blocking and unblocking, invoking {@link
     * #tryAcquireShared} until success.
     *
     * @param arg the acquire argument.  This value is conveyed to
     *            {@link #tryAcquireShared} but is otherwise uninterpreted
     *            and can represent anything you like.
     */
    public final void acquireShared(int arg) {
        if (tryAcquireShared(arg) < 0) doAcquireShared(arg);
    }

    /**
     * Acquires in shared mode, aborting if interrupted.  Implemented
     * by first checking interrupt status, then invoking at least once
     * {@link #tryAcquireShared}, returning on success.  Otherwise the
     * thread is queued, possibly repeatedly blocking and unblocking,
     * invoking {@link #tryAcquireShared} until success or the thread
     * is interrupted.
     *
     * @param arg the acquire argument.
     *            This value is conveyed to {@link #tryAcquireShared} but is
     *            otherwise uninterpreted and can represent anything
     *            you like.
     * @throws InterruptedException if the current thread is interrupted
     */
    public final void acquireSharedInterruptibly(int arg) throws InterruptedException {
        if (Thread.interrupted()) throw new InterruptedException();
        if (tryAcquireShared(arg) < 0) doAcquireSharedInterruptibly(arg);
    }

    /**
     * Attempts to acquire in shared mode, aborting if interrupted, and
     * failing if the given timeout elapses.  Implemented by first
     * checking interrupt status, then invoking at least once {@link
     * #tryAcquireShared}, returning on success.  Otherwise, the
     * thread is queued, possibly repeatedly blocking and unblocking,
     * invoking {@link #tryAcquireShared} until success or the thread
     * is interrupted or the timeout elapses.
     *
     * @param arg          the acquire argument.  This value is conveyed to
     *                     {@link #tryAcquireShared} but is otherwise uninterpreted
     *                     and can represent anything you like.
     * @param nanosTimeout the maximum number of nanoseconds to wait
     * @return {@code true} if acquired; {@code false} if timed out
     * @throws InterruptedException if the current thread is interrupted
     */
    public final boolean tryAcquireSharedNanos(int arg, long nanosTimeout) throws InterruptedException {
        if (Thread.interrupted()) throw new InterruptedException();
        return tryAcquireShared(arg) >= 0 || doAcquireSharedNanos(arg, nanosTimeout);
    }

    /**
     * Releases in shared mode.  Implemented by unblocking one or more
     * threads if {@link #tryReleaseShared} returns true.
     *
     * @param arg the release argument.  This value is conveyed to
     *            {@link #tryReleaseShared} but is otherwise uninterpreted
     *            and can represent anything you like.
     * @return the value returned from {@link #tryReleaseShared}
     */
    public final boolean releaseShared(int arg) {
        if (tryReleaseShared(arg)) {
            doReleaseShared();
            return true;
        }
        return false;
    }

    // Queue inspection methods

    /**
     * Queries whether any threads are waiting to acquire. Note that
     * because cancellations due to interrupts and timeouts may occur
     * at any time, a {@code true} return does not guarantee that any
     * other thread will ever acquire.
     *
     * <p>In this implementation, this operation returns in
     * constant time.
     *
     * @return {@code true} if there may be other threads waiting to acquire
     */
    public final boolean hasQueuedThreads() {
        return head != tail;
    }

    /**
     * Queries whether any threads have ever contended to acquire this
     * synchronizer; that is if an acquire method has ever blocked.
     *
     * <p>In this implementation, this operation returns in
     * constant time.
     *
     * @return {@code true} if there has ever been contention
     */
    public final boolean hasContended() {
        return head != null;
    }

    /**
     * Returns the first (longest-waiting) thread in the queue, or
     * {@code null} if no threads are currently queued.
     *
     * <p>In this implementation, this operation normally returns in
     * constant time, but may iterate upon contention if other threads are
     * concurrently modifying the queue.
     *
     * @return the first (longest-waiting) thread in the queue, or
     * {@code null} if no threads are currently queued
     */
    public final Thread getFirstQueuedThread() {
        // handle only fast path, else relay
        return (head == tail) ? null : fullGetFirstQueuedThread();
    }

    /**
     * Version of getFirstQueuedThread called when fastpath fails
     */
    private Thread fullGetFirstQueuedThread() {
        /*
         * The first node is normally head.next. Try to get its
         * thread field, ensuring consistent reads: If thread
         * field is nulled out or s.prev is no longer head, then
         * some other thread(s) concurrently performed setHead in
         * between some of our reads. We try this twice before
         * resorting to traversal.
         */
        resolve.Node h, s;
        Thread st;
        if (((h = head) != null && (s = h.next) != null && s.prev == head && (st = s.thread) != null) || ((h = head) != null && (s = h.next) != null && s.prev == head && (st = s.thread) != null))
            return st;

        /*
         * Head's next field might not have been set yet, or may have
         * been unset after setHead. So we must check to see if tail
         * is actually first node. If not, we continue on, safely
         * traversing from tail back to head to find first,
         * guaranteeing termination.
         */

        resolve.Node t = tail;
        Thread firstThread = null;
        while (t != null && t != head) {
            Thread tt = t.thread;
            if (tt != null) firstThread = tt;
            t = t.prev;
        }
        return firstThread;
    }

    /**
     * Returns true if the given thread is currently queued.
     *
     * <p>This implementation traverses the queue to determine
     * presence of the given thread.
     *
     * @param thread the thread
     * @return {@code true} if the given thread is on the queue
     * @throws NullPointerException if the thread is null
     */
    public final boolean isQueued(Thread thread) {
        if (thread == null) throw new NullPointerException();
        for (resolve.Node p = tail; p != null; p = p.prev)
            if (p.thread == thread) return true;
        return false;
    }

    /**
     * Returns {@code true} if the apparent first queued thread, if one
     * exists, is waiting in exclusive mode.  If this method returns
     * {@code true}, and the current thread is attempting to acquire in
     * shared mode (that is, this method is invoked from {@link
     * #tryAcquireShared}) then it is guaranteed that the current thread
     * is not the first queued thread.  Used only as a heuristic in
     * ReentrantReadWriteLock.
     */
    final boolean apparentlyFirstQueuedIsExclusive() {
        resolve.Node h, s;
        return (h = head) != null && (s = h.next) != null && !s.isShared() && s.thread != null;
    }

    /**
     * 这个方法将会被公平锁的tryAcquire()调用
     * hasQueuedPredecessors是公平锁加锁时判断等待队列中是否存在有效节点的方法
     * <p>
     * Queries whether any threads have been waiting to acquire longer
     * than the current thread.
     *
     * <p>An invocation of this method is equivalent to (but may be
     * more efficient than):
     * <pre> {@code
     * getFirstQueuedThread() != Thread.currentThread() &&
     * hasQueuedThreads()}</pre>
     *
     * <p>Note that because cancellations due to interrupts and
     * timeouts may occur at any time, a {@code true} return does not
     * guarantee that some other thread will acquire before the current
     * thread.  Likewise, it is possible for another thread to win a
     * race to enqueue after this method has returned {@code false},
     * due to the queue being empty.
     *
     * <p>This method is designed to be used by a fair synchronizer to
     * avoid <a href="resolve#barging">barging</a>.
     * Such a synchronizer's {@link #tryAcquire} method should return
     * {@code false}, and its {@link #tryAcquireShared} method should
     * return a negative value, if this method returns {@code true}
     * (unless this is a reentrant acquire).  For example, the {@code
     * tryAcquire} method for a fair, reentrant, exclusive mode
     * synchronizer might look like this:
     *
     * <pre> {@code
     * protected boolean tryAcquire(int arg) {
     *   if (isHeldExclusively()) {
     *     // A reentrant acquire; increment hold count
     *     return true;
     *   } else if (hasQueuedPredecessors()) {
     *     return false;
     *   } else {
     *     // try to acquire normally
     *   }
     * }}</pre>
     *
     * @return {@code true} if there is a queued thread preceding the
     * current thread, and {@code false} if the current thread
     * is at the head of the queue or the queue is empty
     * @since 1.7
     */
    public final boolean hasQueuedPredecessors() {
        // The correctness of this depends on head being initialized
        // before tail and on head.next being accurate if the current
        // thread is first in queue.
        resolve.Node t = tail; // Read fields in reverse initialization order
        resolve.Node h = head;
        resolve.Node s;
        return h != t && ((s = h.next) == null || s.thread != Thread.currentThread());
    }

    // Instrumentation and monitoring methods

    /**
     * Returns an estimate of the number of threads waiting to
     * acquire.  The value is only an estimate because the number of
     * threads may change dynamically while this method traverses
     * internal data structures.  This method is designed for use in
     * monitoring system state, not for synchronization
     * control.
     *
     * @return the estimated number of threads waiting to acquire
     */
    public final int getQueueLength() {
        int n = 0;
        for (resolve.Node p = tail; p != null; p = p.prev) {
            if (p.thread != null) ++n;
        }
        return n;
    }

    /**
     * Returns a collection containing threads that may be waiting to
     * acquire.  Because the actual set of threads may change
     * dynamically while constructing this result, the returned
     * collection is only a best-effort estimate.  The elements of the
     * returned collection are in no particular order.  This method is
     * designed to facilitate construction of subclasses that provide
     * more extensive monitoring facilities.
     *
     * @return the collection of threads
     */
    public final Collection<Thread> getQueuedThreads() {
        ArrayList<Thread> list = new ArrayList<Thread>();
        for (resolve.Node p = tail; p != null; p = p.prev) {
            Thread t = p.thread;
            if (t != null) list.add(t);
        }
        return list;
    }

    /**
     * Returns a collection containing threads that may be waiting to
     * acquire in exclusive mode. This has the same properties
     * as {@link #getQueuedThreads} except that it only returns
     * those threads waiting due to an exclusive acquire.
     *
     * @return the collection of threads
     */
    public final Collection<Thread> getExclusiveQueuedThreads() {
        ArrayList<Thread> list = new ArrayList<Thread>();
        for (resolve.Node p = tail; p != null; p = p.prev) {
            if (!p.isShared()) {
                Thread t = p.thread;
                if (t != null) list.add(t);
            }
        }
        return list;
    }

    /**
     * Returns a collection containing threads that may be waiting to
     * acquire in shared mode. This has the same properties
     * as {@link #getQueuedThreads} except that it only returns
     * those threads waiting due to a shared acquire.
     *
     * @return the collection of threads
     */
    public final Collection<Thread> getSharedQueuedThreads() {
        ArrayList<Thread> list = new ArrayList<Thread>();
        for (resolve.Node p = tail; p != null; p = p.prev) {
            if (p.isShared()) {
                Thread t = p.thread;
                if (t != null) list.add(t);
            }
        }
        return list;
    }

    /**
     * Returns a string identifying this synchronizer, as well as its state.
     * The state, in brackets, includes the String {@code "State ="}
     * followed by the current value of {@link #getState}, and either
     * {@code "nonempty"} or {@code "empty"} depending on whether the
     * queue is empty.
     *
     * @return a string identifying this synchronizer, as well as its state
     */
    public String toString() {
        int s = getState();
        String q = hasQueuedThreads() ? "non" : "";
        return super.toString() + "[State = " + s + ", " + q + "empty queue]";
    }

    // Internal support methods for Conditions

    /**
     * Returns true if a node, always one that was initially placed on
     * a condition queue, is now waiting to reacquire on sync queue.
     *
     * @param node the node
     * @return true if is reacquiring
     */
    final boolean isOnSyncQueue(resolve.Node node) {
        if (node.waitStatus == resolve.Node.CONDITION || node.prev == null) return false;
        if (node.next != null) // If has successor, it must be on queue
            return true;
        /*
         * node.prev can be non-null, but not yet on queue because
         * the CAS to place it on queue can fail. So we have to
         * traverse from tail to make sure it actually made it.  It
         * will always be near the tail in calls to this method, and
         * unless the CAS failed (which is unlikely), it will be
         * there, so we hardly ever traverse much.
         */
        return findNodeFromTail(node);
    }

    /**
     * Returns true if node is on sync queue by searching backwards from tail.
     * Called only when needed by isOnSyncQueue.
     *
     * @return true if present
     */
    private boolean findNodeFromTail(resolve.Node node) {
        resolve.Node t = tail;
        for (; ; ) {
            if (t == node) return true;
            if (t == null) return false;
            t = t.prev;
        }
    }

    /**
     * Transfers a node from a condition queue onto sync queue.
     * Returns true if successful.
     *
     * @param node the node
     * @return true if successfully transferred (else the node was
     * cancelled before signal)
     */
    final boolean transferForSignal(resolve.Node node) {
        /*
         * If cannot change waitStatus, the node has been cancelled.
         */
        if (!compareAndSetWaitStatus(node, resolve.Node.CONDITION, 0)) return false;

        /*
         * Splice onto queue and try to set waitStatus of predecessor to
         * indicate that thread is (probably) waiting. If cancelled or
         * attempt to set waitStatus fails, wake up to resync (in which
         * case the waitStatus can be transiently and harmlessly wrong).
         */
        resolve.Node p = enq(node);
        int ws = p.waitStatus;
        if (ws > 0 || !compareAndSetWaitStatus(p, ws, resolve.Node.SIGNAL)) LockSupport.unpark(node.thread);
        return true;
    }

    /**
     * Transfers node, if necessary, to sync queue after a cancelled wait.
     * Returns true if thread was cancelled before being signalled.
     *
     * @param node the node
     * @return true if cancelled before the node was signalled
     */
    final boolean transferAfterCancelledWait(resolve.Node node) {
        if (compareAndSetWaitStatus(node, resolve.Node.CONDITION, 0)) {
            enq(node);
            return true;
        }
        /*
         * If we lost out to a signal(), then we can't proceed
         * until it finishes its enq().  Cancelling during an
         * incomplete transfer is both rare and transient, so just
         * spin.
         */
        while (!isOnSyncQueue(node)) Thread.yield();
        return false;
    }

    /**
     * Invokes release with current state value; returns saved state.
     * Cancels node and throws exception on failure.
     *
     * @param node the condition node for this wait
     * @return previous sync state
     */
    final int fullyRelease(resolve.Node node) {
        boolean failed = true;
        try {
            int savedState = getState();
            if (release(savedState)) {
                failed = false;
                return savedState;
            } else {
                throw new IllegalMonitorStateException();
            }
        } finally {
            if (failed) node.waitStatus = resolve.Node.CANCELLED;
        }
    }

    // Instrumentation methods for conditions

    /**
     * Queries whether the given ConditionObject
     * uses this synchronizer as its lock.
     *
     * @param condition the condition
     * @return {@code true} if owned
     * @throws NullPointerException if the condition is null
     */
    public final boolean owns(resolve.ConditionObject condition) {
        return condition.isOwnedBy(this);
    }

    /**
     * Queries whether any threads are waiting on the given condition
     * associated with this synchronizer. Note that because timeouts
     * and interrupts may occur at any time, a {@code true} return
     * does not guarantee that a future {@code signal} will awaken
     * any threads.  This method is designed primarily for use in
     * monitoring of the system state.
     *
     * @param condition the condition
     * @return {@code true} if there are any waiting threads
     * @throws IllegalMonitorStateException if exclusive synchronization
     *                                      is not held
     * @throws IllegalArgumentException     if the given condition is
     *                                      not associated with this synchronizer
     * @throws NullPointerException         if the condition is null
     */
    public final boolean hasWaiters(resolve.ConditionObject condition) {
        if (!owns(condition)) throw new IllegalArgumentException("Not owner");
        return condition.hasWaiters();
    }

    /**
     * Returns an estimate of the number of threads waiting on the
     * given condition associated with this synchronizer. Note that
     * because timeouts and interrupts may occur at any time, the
     * estimate serves only as an upper bound on the actual number of
     * waiters.  This method is designed for use in monitoring of the
     * system state, not for synchronization control.
     *
     * @param condition the condition
     * @return the estimated number of waiting threads
     * @throws IllegalMonitorStateException if exclusive synchronization
     *                                      is not held
     * @throws IllegalArgumentException     if the given condition is
     *                                      not associated with this synchronizer
     * @throws NullPointerException         if the condition is null
     */
    public final int getWaitQueueLength(resolve.ConditionObject condition) {
        if (!owns(condition)) throw new IllegalArgumentException("Not owner");
        return condition.getWaitQueueLength();
    }

    /**
     * Returns a collection containing those threads that may be
     * waiting on the given condition associated with this
     * synchronizer.  Because the actual set of threads may change
     * dynamically while constructing this result, the returned
     * collection is only a best-effort estimate. The elements of the
     * returned collection are in no particular order.
     *
     * @param condition the condition
     * @return the collection of threads
     * @throws IllegalMonitorStateException if exclusive synchronization
     *                                      is not held
     * @throws IllegalArgumentException     if the given condition is
     *                                      not associated with this synchronizer
     * @throws NullPointerException         if the condition is null
     */
    public final Collection<Thread> getWaitingThreads(resolve.ConditionObject condition) {
        if (!owns(condition)) throw new IllegalArgumentException("Not owner");
        return condition.getWaitingThreads();
    }

    /**
     * Condition implementation for a {@link
     * resolve} serving as the basis of a {@link
     * Lock} implementation.
     *
     * <p>Method documentation for this class describes mechanics,
     * not behavioral specifications from the point of view of Lock
     * and Condition users. Exported versions of this class will in
     * general need to be accompanied by documentation describing
     * condition semantics that rely on those of the associated
     * {@code resolve}.
     *
     * <p>This class is Serializable, but all fields are transient,
     * so deserialized conditions have no waiters.
     */
    public class ConditionObject implements Condition, java.io.Serializable {
        private static final long serialVersionUID = 1173984872572414699L;
        /**
         * First node of condition queue.
         */
        private transient resolve.Node firstWaiter;
        /**
         * Last node of condition queue.
         */
        private transient resolve.Node lastWaiter;

        /**
         * Creates a new {@code ConditionObject} instance.
         */
        public ConditionObject() {
        }

        // Internal methods

        /**
         * Adds a new waiter to wait queue.
         *
         * @return its new wait node
         */
        private resolve.Node addConditionWaiter() {
            resolve.Node t = lastWaiter;
            // If lastWaiter is cancelled, clean out.
            if (t != null && t.waitStatus != resolve.Node.CONDITION) {
                unlinkCancelledWaiters();
                t = lastWaiter;
            }
            resolve.Node node = new resolve.Node(Thread.currentThread(), resolve.Node.CONDITION);
            if (t == null) firstWaiter = node;
            else t.nextWaiter = node;
            lastWaiter = node;
            return node;
        }

        /**
         * Removes and transfers nodes until hit non-cancelled one or
         * null. Split out from signal in part to encourage compilers
         * to inline the case of no waiters.
         *
         * @param first (non-null) the first node on condition queue
         */
        private void doSignal(resolve.Node first) {
            do {
                if ((firstWaiter = first.nextWaiter) == null) lastWaiter = null;
                first.nextWaiter = null;
            } while (!transferForSignal(first) && (first = firstWaiter) != null);
        }

        /**
         * Removes and transfers all nodes.
         *
         * @param first (non-null) the first node on condition queue
         */
        private void doSignalAll(resolve.Node first) {
            lastWaiter = firstWaiter = null;
            do {
                resolve.Node next = first.nextWaiter;
                first.nextWaiter = null;
                transferForSignal(first);
                first = next;
            } while (first != null);
        }

        /**
         * Unlinks cancelled waiter nodes from condition queue.
         * Called only while holding lock. This is called when
         * cancellation occurred during condition wait, and upon
         * insertion of a new waiter when lastWaiter is seen to have
         * been cancelled. This method is needed to avoid garbage
         * retention in the absence of signals. So even though it may
         * require a full traversal, it comes into play only when
         * timeouts or cancellations occur in the absence of
         * signals. It traverses all nodes rather than stopping at a
         * particular target to unlink all pointers to garbage nodes
         * without requiring many re-traversals during cancellation
         * storms.
         */
        private void unlinkCancelledWaiters() {
            resolve.Node t = firstWaiter;
            resolve.Node trail = null;
            while (t != null) {
                resolve.Node next = t.nextWaiter;
                if (t.waitStatus != resolve.Node.CONDITION) {
                    t.nextWaiter = null;
                    if (trail == null) firstWaiter = next;
                    else trail.nextWaiter = next;
                    if (next == null) lastWaiter = trail;
                } else trail = t;
                t = next;
            }
        }

        // public methods

        /**
         * Moves the longest-waiting thread, if one exists, from the
         * wait queue for this condition to the wait queue for the
         * owning lock.
         *
         * @throws IllegalMonitorStateException if {@link #isHeldExclusively}
         *                                      returns {@code false}
         */
        public final void signal() {
            if (!isHeldExclusively()) throw new IllegalMonitorStateException();
            resolve.Node first = firstWaiter;
            if (first != null) doSignal(first);
        }

        /**
         * Moves all threads from the wait queue for this condition to
         * the wait queue for the owning lock.
         *
         * @throws IllegalMonitorStateException if {@link #isHeldExclusively}
         *                                      returns {@code false}
         */
        public final void signalAll() {
            if (!isHeldExclusively()) throw new IllegalMonitorStateException();
            resolve.Node first = firstWaiter;
            if (first != null) doSignalAll(first);
        }

        /**
         * Implements uninterruptible condition wait.
         * <ol>
         * <li> Save lock state returned by {@link #getState}.
         * <li> Invoke {@link #release} with saved state as argument,
         *      throwing IllegalMonitorStateException if it fails.
         * <li> Block until signalled.
         * <li> Reacquire by invoking specialized version of
         *      {@link #acquire} with saved state as argument.
         * </ol>
         */
        public final void awaitUninterruptibly() {
            resolve.Node node = addConditionWaiter();
            int savedState = fullyRelease(node);
            boolean interrupted = false;
            while (!isOnSyncQueue(node)) {
                LockSupport.park(this);
                if (Thread.interrupted()) interrupted = true;
            }
            if (acquireQueued(node, savedState) || interrupted) selfInterrupt();
        }

        /*
         * For interruptible waits, we need to track whether to throw
         * InterruptedException, if interrupted while blocked on
         * condition, versus reinterrupt current thread, if
         * interrupted while blocked waiting to re-acquire.
         */

        /**
         * Mode meaning to reinterrupt on exit from wait
         */
        private static final int REINTERRUPT = 1;
        /**
         * Mode meaning to throw InterruptedException on exit from wait
         */
        private static final int THROW_IE = -1;

        /**
         * Checks for interrupt, returning THROW_IE if interrupted
         * before signalled, REINTERRUPT if after signalled, or
         * 0 if not interrupted.
         */
        private int checkInterruptWhileWaiting(resolve.Node node) {
            return Thread.interrupted() ? (transferAfterCancelledWait(node) ? THROW_IE : REINTERRUPT) : 0;
        }

        /**
         * Throws InterruptedException, reinterrupts current thread, or
         * does nothing, depending on mode.
         */
        private void reportInterruptAfterWait(int interruptMode) throws InterruptedException {
            if (interruptMode == THROW_IE) throw new InterruptedException();
            else if (interruptMode == REINTERRUPT) selfInterrupt();
        }

        /**
         * Implements interruptible condition wait.
         * <ol>
         * <li> If current thread is interrupted, throw InterruptedException.
         * <li> Save lock state returned by {@link #getState}.
         * <li> Invoke {@link #release} with saved state as argument,
         *      throwing IllegalMonitorStateException if it fails.
         * <li> Block until signalled or interrupted.
         * <li> Reacquire by invoking specialized version of
         *      {@link #acquire} with saved state as argument.
         * <li> If interrupted while blocked in step 4, throw InterruptedException.
         * </ol>
         */
        public final void await() throws InterruptedException {
            if (Thread.interrupted()) throw new InterruptedException();
            resolve.Node node = addConditionWaiter();
            int savedState = fullyRelease(node);
            int interruptMode = 0;
            while (!isOnSyncQueue(node)) {
                LockSupport.park(this);
                if ((interruptMode = checkInterruptWhileWaiting(node)) != 0) break;
            }
            if (acquireQueued(node, savedState) && interruptMode != THROW_IE) interruptMode = REINTERRUPT;
            if (node.nextWaiter != null) // clean up if cancelled
                unlinkCancelledWaiters();
            if (interruptMode != 0) reportInterruptAfterWait(interruptMode);
        }

        /**
         * Implements timed condition wait.
         * <ol>
         * <li> If current thread is interrupted, throw InterruptedException.
         * <li> Save lock state returned by {@link #getState}.
         * <li> Invoke {@link #release} with saved state as argument,
         *      throwing IllegalMonitorStateException if it fails.
         * <li> Block until signalled, interrupted, or timed out.
         * <li> Reacquire by invoking specialized version of
         *      {@link #acquire} with saved state as argument.
         * <li> If interrupted while blocked in step 4, throw InterruptedException.
         * </ol>
         */
        public final long awaitNanos(long nanosTimeout) throws InterruptedException {
            if (Thread.interrupted()) throw new InterruptedException();
            resolve.Node node = addConditionWaiter();
            int savedState = fullyRelease(node);
            final long deadline = System.nanoTime() + nanosTimeout;
            int interruptMode = 0;
            while (!isOnSyncQueue(node)) {
                if (nanosTimeout <= 0L) {
                    transferAfterCancelledWait(node);
                    break;
                }
                if (nanosTimeout >= spinForTimeoutThreshold) LockSupport.parkNanos(this, nanosTimeout);
                if ((interruptMode = checkInterruptWhileWaiting(node)) != 0) break;
                nanosTimeout = deadline - System.nanoTime();
            }
            if (acquireQueued(node, savedState) && interruptMode != THROW_IE) interruptMode = REINTERRUPT;
            if (node.nextWaiter != null) unlinkCancelledWaiters();
            if (interruptMode != 0) reportInterruptAfterWait(interruptMode);
            return deadline - System.nanoTime();
        }

        /**
         * Implements absolute timed condition wait.
         * <ol>
         * <li> If current thread is interrupted, throw InterruptedException.
         * <li> Save lock state returned by {@link #getState}.
         * <li> Invoke {@link #release} with saved state as argument,
         *      throwing IllegalMonitorStateException if it fails.
         * <li> Block until signalled, interrupted, or timed out.
         * <li> Reacquire by invoking specialized version of
         *      {@link #acquire} with saved state as argument.
         * <li> If interrupted while blocked in step 4, throw InterruptedException.
         * <li> If timed out while blocked in step 4, return false, else true.
         * </ol>
         */
        public final boolean awaitUntil(Date deadline) throws InterruptedException {
            long abstime = deadline.getTime();
            if (Thread.interrupted()) throw new InterruptedException();
            resolve.Node node = addConditionWaiter();
            int savedState = fullyRelease(node);
            boolean timedout = false;
            int interruptMode = 0;
            while (!isOnSyncQueue(node)) {
                if (System.currentTimeMillis() > abstime) {
                    timedout = transferAfterCancelledWait(node);
                    break;
                }
                LockSupport.parkUntil(this, abstime);
                if ((interruptMode = checkInterruptWhileWaiting(node)) != 0) break;
            }
            if (acquireQueued(node, savedState) && interruptMode != THROW_IE) interruptMode = REINTERRUPT;
            if (node.nextWaiter != null) unlinkCancelledWaiters();
            if (interruptMode != 0) reportInterruptAfterWait(interruptMode);
            return !timedout;
        }

        /**
         * Implements timed condition wait.
         * <ol>
         * <li> If current thread is interrupted, throw InterruptedException.
         * <li> Save lock state returned by {@link #getState}.
         * <li> Invoke {@link #release} with saved state as argument,
         *      throwing IllegalMonitorStateException if it fails.
         * <li> Block until signalled, interrupted, or timed out.
         * <li> Reacquire by invoking specialized version of
         *      {@link #acquire} with saved state as argument.
         * <li> If interrupted while blocked in step 4, throw InterruptedException.
         * <li> If timed out while blocked in step 4, return false, else true.
         * </ol>
         */
        public final boolean await(long time, TimeUnit unit) throws InterruptedException {
            long nanosTimeout = unit.toNanos(time);
            if (Thread.interrupted()) throw new InterruptedException();
            resolve.Node node = addConditionWaiter();
            int savedState = fullyRelease(node);
            final long deadline = System.nanoTime() + nanosTimeout;
            boolean timedout = false;
            int interruptMode = 0;
            while (!isOnSyncQueue(node)) {
                if (nanosTimeout <= 0L) {
                    timedout = transferAfterCancelledWait(node);
                    break;
                }
                if (nanosTimeout >= spinForTimeoutThreshold) LockSupport.parkNanos(this, nanosTimeout);
                if ((interruptMode = checkInterruptWhileWaiting(node)) != 0) break;
                nanosTimeout = deadline - System.nanoTime();
            }
            if (acquireQueued(node, savedState) && interruptMode != THROW_IE) interruptMode = REINTERRUPT;
            if (node.nextWaiter != null) unlinkCancelledWaiters();
            if (interruptMode != 0) reportInterruptAfterWait(interruptMode);
            return !timedout;
        }

        //  support for instrumentation

        /**
         * Returns true if this condition was created by the given
         * synchronization object.
         *
         * @return {@code true} if owned
         */
        final boolean isOwnedBy(resolve sync) {
            return sync == resolve.this;
        }

        /**
         * Queries whether any threads are waiting on this condition.
         * Implements {@link resolve#hasWaiters(resolve.ConditionObject)}.
         *
         * @return {@code true} if there are any waiting threads
         * @throws IllegalMonitorStateException if {@link #isHeldExclusively}
         *                                      returns {@code false}
         */
        protected final boolean hasWaiters() {
            if (!isHeldExclusively()) throw new IllegalMonitorStateException();
            for (resolve.Node w = firstWaiter; w != null; w = w.nextWaiter) {
                if (w.waitStatus == resolve.Node.CONDITION) return true;
            }
            return false;
        }

        /**
         * Returns an estimate of the number of threads waiting on
         * this condition.
         * Implements {@link resolve#getWaitQueueLength(resolve.ConditionObject)}.
         *
         * @return the estimated number of waiting threads
         * @throws IllegalMonitorStateException if {@link #isHeldExclusively}
         *                                      returns {@code false}
         */
        protected final int getWaitQueueLength() {
            if (!isHeldExclusively()) throw new IllegalMonitorStateException();
            int n = 0;
            for (resolve.Node w = firstWaiter; w != null; w = w.nextWaiter) {
                if (w.waitStatus == resolve.Node.CONDITION) ++n;
            }
            return n;
        }

        /**
         * Returns a collection containing those threads that may be
         * waiting on this Condition.
         * Implements {@link resolve#getWaitingThreads(resolve.ConditionObject)}.
         *
         * @return the collection of threads
         * @throws IllegalMonitorStateException if {@link #isHeldExclusively}
         *                                      returns {@code false}
         */
        protected final Collection<Thread> getWaitingThreads() {
            if (!isHeldExclusively()) throw new IllegalMonitorStateException();
            ArrayList<Thread> list = new ArrayList<Thread>();
            for (resolve.Node w = firstWaiter; w != null; w = w.nextWaiter) {
                if (w.waitStatus == resolve.Node.CONDITION) {
                    Thread t = w.thread;
                    if (t != null) list.add(t);
                }
            }
            return list;
        }
    }

    /**
     * Setup to support compareAndSet. We need to natively implement
     * this here: For the sake of permitting future enhancements, we
     * cannot explicitly subclass AtomicInteger, which would be
     * efficient and useful otherwise. So, as the lesser of evils, we
     * natively implement using hotspot intrinsics API. And while we
     * are at it, we do the same for other CASable fields (which could
     * otherwise be done with atomic field updaters).
     */
    private static final Unsafe unsafe = Unsafe.getUnsafe();
    private static final long stateOffset;
    private static final long headOffset;
    private static final long tailOffset;
    private static final long waitStatusOffset;
    private static final long nextOffset;

    static {
        try {
            stateOffset = unsafe.objectFieldOffset(resolve.class.getDeclaredField("state"));
            headOffset = unsafe.objectFieldOffset(resolve.class.getDeclaredField("head"));
            tailOffset = unsafe.objectFieldOffset(resolve.class.getDeclaredField("tail"));
            waitStatusOffset = unsafe.objectFieldOffset(resolve.Node.class.getDeclaredField("waitStatus"));
            nextOffset = unsafe.objectFieldOffset(resolve.Node.class.getDeclaredField("next"));

        } catch (Exception ex) {
            throw new Error(ex);
        }
    }

    /**
     * CAS head field. Used only by enq.
     */
    private final boolean compareAndSetHead(resolve.Node update) {
        return unsafe.compareAndSwapObject(this, headOffset, null, update);
    }

    /**
     * CAS tail field. Used only by enq.
     */
    private final boolean compareAndSetTail(resolve.Node expect, resolve.Node update) {
        return unsafe.compareAndSwapObject(this, tailOffset, expect, update);
    }

    /**
     * CAS waitStatus field of a node.
     */
    private static final boolean compareAndSetWaitStatus(resolve.Node node, int expect, int update) {
        return unsafe.compareAndSwapInt(node, waitStatusOffset, expect, update);
    }

    /**
     * CAS next field of a node.
     */
    private static final boolean compareAndSetNext(resolve.Node node, resolve.Node expect, resolve.Node update) {
        return unsafe.compareAndSwapObject(node, nextOffset, expect, update);
    }

}
